Năm 1857, Lưu Vĩnh Phúc xin làm thuộc hạ của Ngô Lăng Vân, người tự xưng là Ngô Vương, và là dư đảng Thái Bình Thiên quốc, bản doanh đóng gần Nam Ninh, Quảng Tây (Trung Quốc). Lưu được Ngô Lăng Vân trợ giúp rồi sau đã trở thành một nhân vật quyền thế dưới trướng của Ngô Vương. Khi Ngô Lăng Vân bị giết (1863), Lưu đem bộ hạ theo Vương Sĩ Lâm và Hoàng Tư Nùng ở châu Thượng Tư (Quảng Tây) cướp phá ở nhiều nơi, sau mới gia nhập lại với Ngô Côn, con trai và là người kế nghiệp Ngô Vương. Là một người có nhiều tham vọng, cộng thêm hoàn cảnh thiếu thốn, Lưu xin với Ngô Á Chung (tức Ngô Côn) đem quân vượt biên giới sang cướp bóc bên Đại Nam. Cuộc quân hành này cũng tránh được quan quân nhà Thanh đang càn quét, tái lập quyền kiểm soát vùng Lưỡng Quảng. Với 200 đồng đảng thân tín, trương một lá cờ màu đen làm kỳ hiệu, Lưu Vĩnh Phúc vượt biên giới vào Đại Nam năm 1865.

Lưu vừa đi vừa tuyển thêm quân từ các toán thổ phỉ khác mà không bị ai chặn lại hay ngăn trở gì. Đến gần Sơn Tây, quân Cờ Đen khi đó đã lên tới 500 người dừng lại lập doanh trại. Sự hiện diện của một đội quân vũ trang trong lãnh thổ của các bộ tộc Mông miền núi là một sự đe dọa với họ, nên xung đột vũ trang đã nổ ra. Quân Cờ Đen phục kích và đánh bại cuộc tấn công của thổ dân, đồng thời giết chết một thủ lĩnh của họ.[1] Viên thủ lĩnh này chống đối chính quyền nhà Nguyễn, nên nhân cơ hội đó nhà Nguyễn chính thức ban cho Lưu chức vị Cửu phẩm bách hộ để tiếp tục công việc bình định vùng này.

Tuy vậy, đánh nhau với người thiểu số không phải là mối quan tâm chính của Lưu, nên năm 1868, Lưu quay ra tranh giành khu vực thị trấn Lào Cai, tức châu Bảo Thắng, một món mồi béo bở, lúc bấy giờ đang nằm dưới sự kiểm soát của các thương gia có vũ trang người Quảng Đông. Quân Cờ Đen tự tiện thu thuế, khai khoáng, cướp bóc khắp nơi, quan quân nhà Nguyễn cũng không ngăn cản được. Quân Cờ Đen còn thiết lập một hệ thống bảo kê, đánh thuế 10% cho các hoạt động thương mại đường thủy dọc sông Hồng. Nguồn lợi từ các hoạt động này lớn tới mức quân Cờ đen nhanh chóng gia tăng lực lượng, với cả một số sĩ quan là các lính đánh thuê châu Âu hay Mỹ, và Lưu sử dụng kinh nghiệm của số người này để biến lực lượng của mình thành một đạo quân đáng gờm.:[2]